1. Field of the Invention
This invention relates to digital maps of the type for displaying road or pathway information, and more particularly toward a method for supplementing a digital map with data to enable various traffic modeling actions and to calculate an energy efficient route that can be offered to a driver.
2. Related Art
Personal navigation devices like that shown generally at 10 in FIG. 1, for example, utilize digital maps combined with accurate positioning data from GPS or other data streams. These devices 10 have been developed for commuters seeking navigation assistance, for businesses trying to minimize transportation costs, and many other useful applications. The effectiveness of such navigation systems is inherently dependent upon the accuracy and completeness of the information provided to it in the forms of digital maps and associated features and attribute data. Likewise, the effectiveness of such navigation systems is also dependent upon accurately and quickly matching the actual, real-world location of the navigation device to a corresponding portion of the digital map. Typically, a navigation system 10 includes a display screen 12 or graphic user interface that portrays a network of streets as a series of line segments, including a center line running approximately along the center of each street or path, as exemplified in FIG. 1. The traveler can then be generally located on the digital map close to or with regard to that center line. Such GPS-enabled personal navigation devices, such as those manufactured by TomTom N.V. (tomtom.com), may be also configured as probes to record its position at regular intervals. Such probe data points comprise a sequence of discrete positions recorded at a particular time of the day taken at intervals of, for example, one second. Of course, other suitable devices may be used to generate probe data points including handheld devices, mobile phones, PDAs, and the like.
Maximizing energy efficiency is a universal goal. It is known, for example, that vehicles driven with frequent start-stop type motions are very energy inefficient due to the acceleration and deceleration aspects of this type of driving. Conversely, maintaining a vehicle at a steady speed, particularly in the range of about 45-60 mph, is far more energy efficient.
Navigation devices are well known for their ability to plan a route between two locations in a digital map. For example, as shown in FIG. 2, a traveler originating in Detroit may select a destination of Los Angeles in the digital map and activate an algorithm to calculate a route between the two locations. When alternate routes are possible, such route planning may be carried out on the basis of the shortest distance between origination and destination points. Or, if links in the network include associated travel time attributes, it is possible to recommend the route which indicates the shortest travel time. Other variables may include planning a route based on points of interest, and the like.
Some prior art devices have proposed the calculation of a route between origination and destination points based on fuel economy, carbon footprint and fuel pricing. For example, the ecoRoute™ offered by Garmin Ltd. uses information from a particular vehicle profile to calculate a fuel consumption estimation. That is, the user inputs details about their specific vehicle's fuel economy in both city and highway settings, selects a fuel type relative to the vehicle, and perhaps provides additional details. The system algorithm then calculates fuel consumption estimates based upon the distance to be traveled along a planned route. One particular shortcoming of this approach is that it does not rely on any speed or acceleration attribute associated with the network of links in a digital map database. Therefore, the ecoRouting function is not particularly useful as a representative planning tool. Thus, in referring then to the example of FIG. 2, a driver wishing to travel between Detroit and Los Angeles is not able to intelligently assess the most economical route to travel. Furthermore, programs like the ecoRoute™ require some burdensome user interaction with the navigation device and user knowledge about the vehicle characteristics, fuel prices, etc.
As suggested previously, it is known to take probe data points from low-cost positioning systems in handheld devices and mobile phones with integrated GPS functionality for the purpose of incrementally learning a map using certain clustering technologies. The input to be processed consists of recorded GPS traces, perhaps in the form of a standard ASCII stream or binary file. The output may be a road map in the form of a directed graph with nodes and links associated with travel time information. The probe data, which creates the nodes or probe positions at regular intervals, can be transmitted to a collection service or other map making or data analysis service. Through this method, wherein large populations of probe data are analyzed, road geometry can be inferred and other features and attributes derived by appropriate algorithms.
FIG. 3 is a representative example of raw probe data collected over a period of days from a downtown, city-center area of Ottawa, Canada. From this raw probe data, even an untrained eye can begin to discern road geometries. Each data point represented in the illustration of FIG. 3 includes information as to the particular time of day that the data point was recorded. Thus, while FIG. 3 depicts only longitudinally and laterally dispersed position data, the recorded data also provides a time stamp for each position. Furthermore, each individual probe may create a trace which can be analyzed for travel speeds, accelerations, stops, and the like.
Traditional routing methods use maximum speed limits as exist along road segments to calculate travel time estimates, however in practice speed limit information is not accurate because these speeds are not always possible at various times of the day. Speed profiles have been derived by intensively processing this probe data to create average traffic speeds for each road segment, i.e., for each section of road in the digital map, for different time slots or times of the day. See, for example, the TomTom IQ Routes™ product.
The IQ Routes™ product uses anonymous probe data to discover actual patterns in driving speeds. Typically, route calculations before IQ Routes used 0.85% of the maximum speed limit in its calculation—IQ Routes by contrast uses the speeds actually driven on those roads. (Alternatively, a likely speed value can be derived from the road classification. E.g. when legal speed limits are not available.) This data is applied to a profile model and patterns in the road speeds are identified in time spans (e.g., 5 minute increments) throughout the day. The speed profiles are applied to the road segments, building up an accurate picture of speeds using historical data. All of these speed profiles are added to the existing IQ Routes data built into the map stored in the navigation device 10, to make it even more accurate and useful for premium routing and travel time estimates. Speed profiles therefore represent a continuous or semi-continuous averaged speed distribution of vehicles derived from probe information, driving along the same section of the road and direction. Speed profiles reflect speed variations per segment per time interval, but are not longitudinally distributed in the sense that they do not describe velocity variations along the length of a link or road segment. This information can be used by a navigation system as a cost factor in connection with calculating optimal routes and providing travel/arrival time estimates.
While very useful, these prior art techniques do not provide any indication of the most efficient route between two locations represented in a digital map. Therefore, there is a need to create new and improved methods for computing routes between an origin and destination location which provides the most energy efficient strategy, and which accounts for real life conditions including both static and dynamic elements. Static elements may include features that affect traffic speed including for example sharp bends in the road, traffic controls, and other measures that affect traffic speed as a matter of geometry. Dynamic elements include traffic volumes which fluctuate during workdays with local rush hour conditions, and are affected by weekend travel, holidays and the like. There is also a need to create new and improved data that can be used in connection with a digital map, either as a separate interfacing database or as data augmented directly into an existing map database, to enable traffic modeling applications.